package tree;

import java.sql.Connection;
import java.util.*;

/**
 * @Author leecho
 * @Date: 2021/10/27 13:13
 * @Version 1.0
 */

public class HuffmanTreeDemo {
    public static void main(String[] args) {
        int[] arr = {13,7,8,3,29,6,1};
        HuffmanTree huffmanTree = new HuffmanTree();
        HuffmanTreeNode node = huffmanTree.huffmanTree(arr);
        node.infixList();
    }
}

/*
* 思路
*- 创建二叉树节点类
*   - 数据域和左右两个指向域
*   - 继承接口 -- Comparable 来重写其中的排序规则
* - 创建赫夫曼二叉树类
*   - 二叉树本身是将有序的数组转换得到
*   - 设置一个新的结点list来存储每一个节点
*   - 结点list的值用传入的数组来赋值
*   - 取出最小的两个为左右两个叶子节点，新建一个父节点来创建一颗简单的二叉树
*   - 从list中移除取出的两个左右节点并加入新的父节点
*   - 排序
*   - 重复上面的操作，直到list中只存在一个节点停止
* - 编写主方法，测试
* - 编写一个前序遍历的方法，输出结果验证
* */
class HuffmanTree{
    public HuffmanTreeNode huffmanTree(int[] arr){
        List<HuffmanTreeNode> list = new ArrayList<>();
        HuffmanTreeNode leftNode = null;
        HuffmanTreeNode rightNode = null;

        for (int i : arr) {
            list.add(new HuffmanTreeNode(i));
        }

        while (list.size() > 1){
            Collections.sort(list);

            leftNode = list.get(0);
            rightNode = list.get(1);

            HuffmanTreeNode parent = new HuffmanTreeNode(leftNode.value + rightNode.value);

            parent.left = leftNode;
            parent.right = rightNode;

            list.remove(leftNode);
            list.remove(rightNode);

            list.add(parent);
        }
        return list.get(0);
    }

}

class HuffmanTreeNode implements Comparable<HuffmanTreeNode>{
    int value;
    HuffmanTreeNode left;
    HuffmanTreeNode right;

    public HuffmanTreeNode(int value) {
        this.value = value;
    }

    public void infixList(){
        System.out.printf("%3d",this.value);
        if (this.left != null){
            this.left.infixList();
        }
        if (this.right != null){
            this.right.infixList();
        }
    }

    @Override
    public int compareTo(HuffmanTreeNode o) {
        return this.value - o.value;
    }

    @Override
    public String toString() {
        return "HuffmanTreeNode{" +
                "value=" + value +
                '}';
    }
}